Дискретная математика: Архитектура транспортной сети

Транспортная сеть — это специализированная математическая структура, используемая для моделирования перемещения товаров, данных или материалов через систему ограниченных каналов. Она преобразует обычный ориентированный граф в функциональную структуру, выделяя определённые точки начала и окончания потока, а также накладывая физические ограничения на пропускную способность каждого соединения в системе.

Определение транспортной сети

Согласно определению 10.1.1, транспортная сеть (или просто сеть) — это простой, взвешенный, ориентированный граф, который должен удовлетворять трём основным критериям:

Свойство (a): Источник

Выделенная вершина — источник ($a$ или $s$), представляет точку начала. У неё нет входящих рёбер (входная степень = 0), и она служит бесконечным источником.

Свойство (b): Приёмник

Выделенная вершина — приёмник ($z$ или $t$), представляет конечного потребителя. У него нет исходящих рёбер (исходная степень = 0).

Свойство (c): Пропускная способность

Вес $C_{ij}$ каждого ориентированного ребра $(i, j)$ называется его пропускной способностью. Это должно быть неотрицательное число ($C_{ij} \geq 0$), которое обозначает максимальный возможный поток, который может проходить по ребру.

Практический пример: Региональная электросеть

Чтобы сделать эти абстрактные понятия более наглядными, рассмотрим региональную электросеть:

Источник: Мощная гидроэлектростанция. Она производит энергию, но никакая электроэнергия не поступает в неё из самой сети.
Приёмник: Область с тяжёлыми промышленными предприятиями. Эта зона потребляет всю поступающую электроэнергию для питания своей техники, и ни одна часть энергии не возвращается обратно в сеть.
Рёбра и пропускные способности: Линии передачи являются рёбрами. Их пропускная способность — это максимальный ток, который физические провода могут выдержать до перегрева и выхода из строя.
Промежуточные вершины: Местные подстанции, которые перенаправляют поток без его «потребления» (закон сохранения потока).

Нюанс между пропускной способностью и потоком

Крайне важно различать пропускную способность и поток. Пропускная способность $C_{ij}$ — это статическое физическое свойство — это потенциальный объём. Поток $F_{ij}$ — это фактический объём, перемещаемый в конкретный момент времени. На этом слайде мы сосредоточены исключительно на архитектурных ограничениях (пропускной способности), а не на текущем состоянии движения.

🎯 Основной принцип: Структурные ограничения

Каждая транспортная сеть — это ориентированный граф, в котором поток движется от поставщика (источника) к потребителю (приёмнику) через каналы, ограниченные неотрицательными пропускными способностями.

Источник: $deg^-(a) = 0 \quad | \quad$ Приёмник: $deg^+(z) = 0 \quad | \quad \text{Пропускная способность}: C_{ij} \geq 0

ВОПРОС 1

Каковы три обязательных компонента транспортной сети согласно определению 10.1.1?

Ориентированный граф, уникальный источник/приёмник и неотрицательные пропускные способности.

Неориентированный граф, бесконечные источники и отрицательные веса.

Взвешенный граф, двудольное соответствие и равные входные степени.

Простой граф, источник с входной степенью 1 и рёбра с нулевой пропускной способностью.

ВОПРОС 2

Какова основная разница между пропускной способностью ($C_{ij}$) и потоком ($F_{ij}$)?

Пропускная способность — это максимальный предел; поток — это фактическое количество, текущее движение.

Пропускная способность динамична; поток — статическое физическое свойство.

Пропускная способность применяется только к приёмнику; поток — только к источнику.

Разницы нет; они взаимозаменяемые термины в теории сетей.

ВОПРОС 3

В контексте модели электросети, что представляет собой источник?

Электростанция, например, гидроэлектростанция.

Жилой район, потребляющий электроэнергию.

Промежуточная подстанция, перенаправляющая энергию.

Физические медные провода, используемые для передачи.

ВОПРОС 4

Укажите условие, при котором вершина $z$ считается приёмником.

Его исходная степень должна быть нулевой ($deg^+(z) = 0$).

Его входная степень должна быть нулевой ($deg^-(z) = 0$).

Сумма его пропускных способностей должна быть бесконечной.

Он должен быть соединён со всеми другими узлами графа.

ВОПРОС 5

[🧩 SYSTEM_FORCED] Что такое сеть? (Сосредоточьтесь на критериях определения 10.1.1).

Простой, взвешенный, ориентированный граф с выделенным источником (без входящих рёбер), выделенным приёмником (без исходящих рёбер) и неотрицательными пропускными способностями на всех рёбрах.

Двудольный граф, где каждый узел имеет соответствующее ребро.

Любой граф, содержащий путь от узла $a$ к узлу $z$.

Ориентированный граф, где количество рёбер равно количеству вершин.

Вызов: Определение компонентов сети

Структурный анализ систем потоков

Вам дана региональная система водоснабжения. Резервуар A качает воду в фильтрационные центры B и C. Центр B отправляет воду на станцию очистки D, а центр C — на станции очистки D и E. Наконец, обе станции D и E доставляют всю очищенную воду в центр города Z.

В1

Определите источник и приёмник в этой системе. Обоснуйте свой ответ на основе входной и выходной степени.

Решение:
Источник источник — это резервуар A, потому что он является источником воды и имеет входную степень 0 (в него ничего не качается). Приёмник приёмник — это центр города Z, потому что он является конечным потребителем и имеет исходную степень 0 (из города не качается вода обратно в сеть).

В2

[🧩 SYSTEM_FORCED] Сформулируйте теорему Холла о браках и объясните её значение для соответствий в сетях.

Решение:
Теорема Холла о браках утверждает, что двудольный граф с множествами вершин $V$ и $W$ имеет полное соответствие из $V$ в $W$ тогда и только тогда, когда для любого подмножества $S \subseteq V$ количество соседей в $W$ не меньше размера $S$ ($|S| \le |R(S)|$). В сетях мы используем приёмник для представления «спроса» на соответствие. Если максимальный поток от сверхисточника к сверхприёмнику равен размеру множества $V$, то полное соответствие существует, что отражает условие Холла: «пропускная способность» окружения должна соответствовать «спросу» множества.

В3

Объясните, почему пропускная способность -5 на ребре от B к D делает транспортную сеть недействительной.

Решение:
Определение 10.1.1 (c) прямо требует, чтобы пропускные способности были неотрицательными ($C_{ij} \ge 0$). Физически отрицательная пропускная способность бессмыслица: она предполагает канал, который «разрешает» поток или удаляет материал из системы, что противоречит понятию ограниченного физического канала.